package TestDemo11;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Test {
    public static  ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        HashMap<Integer,Integer> hash=new HashMap();
        int lastIndex=num.length-1;
        if(num.length < 3) return ans;
        if(num.length == 3){
            ArrayList<Integer> line = new ArrayList<Integer>();
            if(num[0]+num[1]+num[2] == 0){
                line.add(num[0]);
                line.add(num[1]);
                line.add(num[2]);
            }
            ans.add(line);
            return ans;
        }

        Arrays.sort(num);
        //放进hash表中去重
        for(int i=0;i<num.length;i++){
            if(!hash.containsValue(num[i])){
                hash.put(i,num[i]);
            }
        }
        for (Map.Entry<Integer,Integer> entry:hash.entrySet()) {
            ArrayList<Integer> line = new ArrayList<Integer>();
            int index=entry.getKey();
            int tar= entry.getValue();
            int head=0;
            int last= num.length-1;
            while(head<=last){
                if(head == index){
                    head++;
                    continue;
                }
                if (last == index){
                    last--;
                    continue;
                }
                if(num[head] + num[last] > -tar){
                    last--;
                }else if(num[head] + num[last] < -tar){
                    head++;
                }else {
                    line.add(num[head]);
                    line.add(num[last]);
                    line.add(tar);
                    head++;
                    last--;
                }
            }
            line.sort((o1,o2)->{
                return o1-o2;
            });
            if(line.size()!=0 && !ans.contains(line)){
                ans.add(line);
            }
        }
        return ans;
    }


    public static void main1(String[] args) {
        ArrayList<Integer> list=new ArrayList<>();
        list.add(-2);
        list.add(-3);
        list.add(2);
        list.sort((o1,o2)->{
            return o1-o2;
        });
        System.out.println("Scasdva");
    }
    public static void main(String[] args) {
        int[] num={-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
        ArrayList<ArrayList<Integer>> ans=threeSum(num);
        System.out.println("scsdavdvsadc");
    }
}
